Chapter 2. Quantum Parallelism and Early Algorithms

In Chapter 1, we learned the Hadamard (H) gate that creates qubit superposition and the CNOT gate that creates entanglement. The remarkable power of quantum algorithms comes from combining these two concepts, superposition and interference.

In this chapter, we learn the principle of quantum parallelism, which allows quantum computers to compute numerous input values simultaneously with a single operation. We also explore the first algorithms that are clearly faster than classical computers—Deutsch-Jozsa and Simon algorithms—using this parallelism. These algorithms are not useful in their own right, but serve as key demonstrations of how quantum computers operate differently from classical computers.

1. Fundamental Concepts

  • Quantum Parallelism: When \(n\) qubits pass through the Hadamard (H) gate, they enter a state where all \(2^n\) possible input states (\(|00\dots 0\rangle\) to \(|11\dots 1\rangle\)) are uniformly superposed. \[H^{\otimes n}|0\rangle^{\otimes n} = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1} |x\rangle\] If this superposed state undergoes a single application of a quantum operation (\(U_f\)) that computes the function \(f(x)\), all \(2^n\) values of \(f(x)\) are computed simultaneously and in parallel, stored in the state.

  • Function Evaluation & Oracle: A quantum circuit that computes a classical function \(f(x)\) is called an Oracle or black box (\(U_f\)). Rather than transforming the input \(|x\rangle\) into \(|f(x)\rangle\), the oracle adds the value to a separate output register (to maintain unitary properties). \[U_f : |x\rangle |y\rangle \mapsto |x\rangle |y \oplus f(x)\rangle\] (Here, \(\oplus\) denotes XOR, i.e., addition modulo 2.)

  • Phase Kickback: A key technique for reading out the results of quantum parallelism. If the output register is prepared in the state \(|-\rangle = \frac{|0\rangle-|1\rangle}{\sqrt{2}}\), the value of \(f(x)\) returns to the phase of the input register rather than the output register. \[U_f |x\rangle |-\rangle = (-1)^{f(x)} |x\rangle |-\rangle\]

    Detailed Explanation: Why does Phase Kickback occur? Assume \(f(x)\) is either 0 or 1.
    • If \(f(x)=0\): \(U_f |x\rangle |-\rangle = |x\rangle |y \oplus 0\rangle = |x\rangle |y\rangle\). \(|-\rangle = \frac{|0\rangle-|1\rangle}{\sqrt{2}} \implies \frac{|0\oplus 0\rangle - |1\oplus 0\rangle}{\sqrt{2}} = \frac{|0\rangle - |1\rangle}{\sqrt{2}} = |-\rangle\). Result: \(|x\rangle |-\rangle \to |x\rangle |-\rangle\). (No change \(\implies (-1)^0\) multiplication)
    • If \(f(x)=1\): \(U_f |x\rangle |-\rangle = |x\rangle |y \oplus 1\rangle\). \(|-\rangle = \frac{|0\rangle-|1\rangle}{\sqrt{2}} \implies \frac{|0\oplus 1\rangle - |1\oplus 1\rangle}{\sqrt{2}} = \frac{|1\rangle - |0\rangle}{\sqrt{2}} = -|-\rangle\). Result: \(|x\rangle |-\rangle \to -|x\rangle |-\rangle\). (Global phase flip \(\implies (-1)^1\) multiplication)

    Through this trick, the value of \(f(x)\) is ‘displayed’ in the coefficient of \(|x\rangle\).

  • Deutsch-Jozsa Problem: Given an \(n\)-bit input, 1-bit output function \(f: \{0,1\}^n \to \{0,1\}\) that is guaranteed to be constant (all \(x\) have the same \(f(x)\), either 0 or 1) or balanced (exactly half of all \(x\) have \(f(x)=0\), and the other half have \(f(x)=1\)), the problem is to determine whether the function is constant or balanced with only one oracle call. (Classically, \(2^{n-1}+1\) calls are required in the worst case)

2. Symbols and Key Equations

  • N-qubit Hadamard Transform: \[H^{\otimes n} |0\rangle^{\otimes n} = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1} |x\rangle\]

  • Oracle \(U_f\) (Standard Oracle): \[U_f |x, y\rangle = |x, y \oplus f(x)\rangle\]

  • Phase Oracle (Equivalent expression of \(U_f\) using phase kick-back): \[U_f \left( \frac{1}{\sqrt{2^n}}\sum_{x} |x\rangle \right) |-\rangle = \left( \frac{1}{\sqrt{2^n}}\sum_{x} (-1)^{f(x)} |x\rangle \right) |-\rangle\]

  • Final State of the Deutsch-Jozsa Algorithm: After applying the algorithm (H \(\to U_f \to\) H), the final state \(|\psi_f\rangle\) of the input register is as follows: \[|\psi_f\rangle = \frac{1}{\sqrt{2^n}}\sum_{y=0}^{2^n-1} \left[ \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1} (-1)^{f(x) \oplus x \cdot y} \right] |y\rangle\] (Here, \(x \cdot y\) is the bitwise dot product.)

3. Easy Examples (Examples with Deeper Insight)

Example 1: Deutsch Algorithm (n=1)

  • Problem: \(f: \{0,1\} \to \{0,1\}\) (1-bit function) is constant (\(f(0)=f(1)\)) or balanced (\(f(0)\neq f(1)\)) determine with a single oracle call.

    • Circuit: \(|0\rangle \longrightarrow [H] \longrightarrow |\quad| \longrightarrow [H] \longrightarrow \text{measurement}\) \(|1\rangle \longrightarrow [H] \longrightarrow |U_f| \longrightarrow [ ] \longrightarrow\)

    • Calculation (Step-by-step):

      1. Initial State: \(|\psi_0\rangle = |01\rangle\)
      2. H Gate Application: \(|\psi_1\rangle = (H|0\rangle) \otimes (H|1\rangle) = |+\rangle \otimes |-\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \otimes \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)\) \(= \frac{1}{2}(|0\rangle(|0\rangle-|1\rangle) + |1\rangle(|0\rangle-|1\rangle))\)
      3. Oracle \(U_f\) Application (Phase Kickback): \(|\psi_2\rangle = \frac{1}{\sqrt{2}} \left( (-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle \right) \otimes |-\rangle\)
      4. Last H Gate Application (Only on Input Register): \(|\psi_3\rangle = \frac{1}{\sqrt{2}} \left( (-1)^{f(0)}H|0\rangle + (-1)^{f(1)}H|1\rangle \right) \otimes |-\rangle\) \(= \frac{1}{\sqrt{2}} \left( (-1)^{f(0)}\frac{|0\rangle+|1\rangle}{\sqrt{2}} + (-1)^{f(1)}\frac{|0\rangle-|1\rangle}{\sqrt{2}} \right) \otimes |-\rangle\) \(= \frac{1}{2} \left( [(-1)^{f(0)} + (-1)^{f(1)}] |0\rangle + [(-1)^{f(0)} - (-1)^{f(1)}] |1\rangle \right) \otimes |-\rangle\)
      5. Measurement (First Qubit):

    • 💡 Detailed Explanation (Case Analysis):

      • Case 1: \(f\) is Constant Since \(f(0) = f(1)\), \((-1)^{f(0)} = (-1)^{f(1)}\). \(|\psi_3\rangle = \frac{1}{2} ( [\pm 2] |0\rangle + [0] |1\rangle ) \otimes |-\rangle = \pm |0\rangle \otimes |-\rangle\). Measuring the first qubit always yields \(|0\rangle\).
      • Case 2: \(f\) is Balanced Since \(f(0) \neq f(1)\), \((-1)^{f(0)} = -(-1)^{f(1)}\). \(|\psi_3\rangle = \frac{1}{2} ( [0] |0\rangle + [\pm 2] |1\rangle ) \otimes |-\rangle = \pm |1\rangle \otimes |-\rangle\). Measuring the first qubit always yields \(|1\rangle\). Conclusion: We calculated \(2^n=2\) values of \(f(x)\) with a single oracle call (parallelism) and then converged to a single answer of \(|0\rangle\) or \(|1\rangle\) through interference using the H gate.

Example 2: Deutsch-Jozsa Algorithm (n-bit)

  • Situation: When the n-bit function \(f\) is constant or balanced, apply \(n\) H gates \(\to U_f \to n\) H gates.

  • Final State Analysis: \(|\psi_f\rangle = \frac{1}{\sqrt{2^n}}\sum_{y} \left[ \frac{1}{\sqrt{2^n}}\sum_{x} (-1)^{f(x) \oplus x \cdot y} \right] |y\rangle\) We measure the entire input register, not the first qubit.

  • Measurement Result (Amplitude of \(y=|00\dots 0\rangle\) state): If \(y=0\), then \(x \cdot y = 0\). The amplitude \(C_0\) of the \(y=0\) state (\(|0\rangle^{\otimes n}\)) is \(C_0 = \frac{1}{2^n} \sum_{x} (-1)^{f(x)}\)

  • 💡 Detailed Explanation (Case Analysis):

    • Case 1: \(f\) is Constant All \(f(x)\) are the same, either 0 or 1. \(C_0 = \frac{1}{2^n} \sum_{x} (\pm 1) = \frac{1}{2^n} (2^n \cdot (\pm 1)) = \pm 1\). The probability \(P_0 = |C_0|^2 = 1\) of measuring the \(|0\rangle^{\otimes n}\) state. The measurement result is always \(|00\dots 0\rangle\).
    • Case 2: \(f\) is Balanced There are \(2^{n-1}\) values of \(x\) where \(f(x)=0\) and \(2^{n-1}\) values where \(f(x)=1\). \(C_0 = \frac{1}{2^n} ( (2^{n-1} \cdot 1) + (2^{n-1} \cdot (-1)) ) = 0\). The probability \(P_0 = |C_0|^2 = 0\) of measuring the \(|0\rangle^{\otimes n}\) state. The measurement result is never \(|00\dots 0\rangle\) (a different state appears).

    Conclusion: By performing a single measurement, if the result is \(|00\dots 0\rangle\), the function is constant; otherwise, it is balanced. We solved a task that classically requires \(2^{n-1}+1\) operations in just one step.

Example 3: Simon’s Algorithm

  • Problem: The \(n\)-bit function \(f(x)\) satisfies \(f(x) = f(y) \iff y = x \oplus s\) (XOR relation) for some hidden bitstring \(s \neq 0\). Find \(s\).

    • Algorithm: Similar to Deutsch-Jozsa, apply \(H \to U_f \to H\).

    • Core Result: The measured bitstring \(y\) always satisfies \(s \cdot y = 0 \pmod 2\) (orthogonal to the hidden \(s\)).

    • 💡 Detailed Explanation (Inspiration from Shor’s Algorithm):

      Classically, finding \(s\) requires randomly sampling \(x\) and finding pairs with equal \(f(x)\), taking exponential time. A quantum computer repeats the \(H \to U_f \to H\) process \(n-1\) times, obtaining \(n-1\) independent \(y_k\) values satisfying \(s \cdot y_1 = 0, s \cdot y_2 = 0, \dots, s \cdot y_{n-1} = 0\). This is equivalent to solving \(n-1\) linear equations for \(s\), uniquely determining \(s\) (classical post-processing). Simon’s algorithm addresses a more practical problem (period finding) than Deutsch-Jozsa, directly inspiring the Shor’s factorization algorithm to be learned in Chapter 4.

4. Practice Problems

  1. Phase Kickback Proof: Compute \(U_f |x\rangle |+\rangle\) (\(|+\rangle = \frac{|0\rangle+|1\rangle}{\sqrt{2}}\)) and show that phase kickback does not occur in this case.
  2. Deutsch Algorithm (Manual Calculation): When \(f(x)\) is constant (\(f(0)=1, f(1)=1\)), step-by-step compute \(|\psi_3\rangle\) from Example 1 to confirm that the final state is \(|0\rangle\).
  3. Oracle Design (n=2): There is a function \(f(x_1 x_0) = x_1\) (returning only the first bit of a 2-bit input). Draw a circuit using basic gates like CNOT to implement the oracle \(U_f\).
  4. Simon’s Algorithm (n=2): Assume \(n=2\) and the hidden \(s=11\) (i.e., \(f(00)=f(11), f(01)=f(10)\)). What \(y\) values can be measured after one run of the algorithm, and why?

5. Solutions

  1. \(U_f |x\rangle |+\rangle = |x\rangle |y \oplus f(x)\rangle\).
    • \(f(x)=0\): \(|x\rangle \frac{|0\oplus 0\rangle + |1\oplus 0\rangle}{\sqrt{2}} = |x\rangle |+\rangle\).
    • \(f(x)=1\): \(|x\rangle \frac{|0\oplus 1\rangle + |1\oplus 1\rangle}{\sqrt{2}} = |x\rangle \frac{|1\rangle + |0\rangle}{\sqrt{2}} = |x\rangle |+\rangle\). In both cases, the same \(|x\rangle |+\rangle\) is obtained. The phase is not inverted.
  2. \(f(0)=1, f(1)=1 \implies (-1)^{f(0)}=-1, (-1)^{f(1)}=-1\). \(|\psi_3\rangle = \frac{1}{2} ( [(-1) + (-1)] |0\rangle + [(-1) - (-1)] |1\rangle ) \otimes |-\rangle\) \(= \frac{1}{2} ( [-2] |0\rangle + [0] |1\rangle ) \otimes |-\rangle = -|0\rangle \otimes |-\rangle\). When measuring the first qubit (ignoring the global phase), \(|0\rangle\) is obtained with 100% probability.
  3. Input \(|x_1 x_0\rangle\), output \(|y\rangle\). \(U_f |x_1 x_0, y\rangle = |x_1 x_0, y \oplus x_1\rangle\). This is a CNOT gate where \(x_1\) is the control qubit and \(y\) is the target qubit. \(x_0\) is not connected to any gate. Circuit: \(x_1 \to \bullet \to\) \(x_0 \to \text{----} \to\) \(y \to \oplus \to\)
  4. The measurement result \(y=y_1 y_0\) must satisfy \(s \cdot y = 0 \pmod 2\). Since \(s=11\), \(s \cdot y = (1 \cdot y_1) \oplus (1 \cdot y_0) = y_1 \oplus y_0 = 0 \pmod 2\). When \(y_1 \oplus y_0 = 0\), this means \(y_1 = y_0\), i.e., \(y=00\) or \(y=11\). Therefore, the only possible measurement results are \(|00\rangle\) or \(|11\rangle\).